package com.yangli.leecode.mashib.interview;

/**
 * @Description https://leetcode.cn/problems/sudoku-solver/
 * @Author liyang
 * @Date 2023/3/9 15:41
 */
public class Forty {
    public static void main(String[] args){
        char[][] board = new char[][]{{'5', '3', '.', '.', '7', '.', '.', '.', '.'}, {'6', '.', '.', '1', '9', '5', '.', '.', '.'}, {'.', '9', '8', '.', '.', '.', '.', '6', '.'}, {'8', '.', '.', '.', '6', '.', '.', '.', '3'}, {'4', '.', '.', '8', '.', '3', '.', '.', '1'}, {'7', '.', '.', '.', '2', '.', '.', '.', '6'}, {'.', '6', '.', '.', '.', '.', '2', '8', '.'}, {'.', '.', '.', '4', '1', '9', '.', '.', '5'}, {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};
        System.out.println(Forty.isValidSudoku(board));
        if (Forty.isValidSudoku(board)) {
            Forty.solveSudoku(board);
        }

        System.out.println(Forty.countAndSay(10));

    }

    // 0036
    public static boolean isValidSudoku(char[][] board){
        boolean[][] row = new boolean[9][10];//表示1-9行即0-8中的j数据有没有出现过
        boolean[][] clo = new boolean[9][10];
        boolean[][] bucket = new boolean[9][10];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                int but = 3 * (i / 3) + j / 3;
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    if (row[i][num] || clo[j][num] || bucket[but][num]) {
                        return false;
                    }
                    row[i][num] = true;
                    clo[j][num] = true;
                    bucket[but][num] = true;
                }

            }
        }
        return true;
    }

    //0037
    public static void solveSudoku(char[][] board){
        boolean[][] row = new boolean[9][10];//表示1-9行即0-8中的j数据有没有出现过
        boolean[][] clo = new boolean[9][10];
        boolean[][] bucket = new boolean[9][10];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                int but = 3 * (i / 3) + j / 3;
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    row[i][num] = true;
                    clo[j][num] = true;
                    bucket[but][num] = true;
                }

            }
        }
        if (process(board, 0, 0, row, clo, bucket)) {
            System.out.println(board[0]);
            System.out.println(board[1]);
            System.out.println(board[2]);
            System.out.println(board[3]);
            System.out.println(board[4]);
            System.out.println(board[5]);
            System.out.println(board[6]);
            System.out.println(board[7]);
            System.out.println(board[8]);

        }
    }

    public static boolean process(char[][] board, int i, int j, boolean[][] row, boolean[][] clo, boolean[][] bucket){
        if (i == 9) {
            return true;
        }
        int nexti = j == 8 ? i + 1 : i;
        int nextj = j == 8 ? 0 : j + 1;
        if (board[i][j] != '.') {
            return process(board, nexti, nextj, row, clo, bucket);
        } else {
            int but = 3 * (i / 3) + j / 3;

            for (int n = 1; n <= 9; n++) {
                if (!row[i][n] && !clo[j][n] && !bucket[but][n]) {
                    row[i][n] = true;
                    clo[j][n] = true;
                    bucket[but][n] = true;
                    board[i][j] = (char) (n + '0');
                    if (process(board, nexti, nextj, row, clo, bucket)) {
                        return true;
                    }
                    row[i][n] = false;
                    clo[j][n] = false;
                    bucket[but][n] = false;
                    board[i][j] = '.';

                }

            }
        }
        return false;


    }

    // 外观数列 0038 https://leetcode.cn/problems/count-and-say/
    public static String countAndSay(int n){
        String ans = "1";
        for (int i = 2; i <= n; i++) {
            ans = count(ans);
        }
        return ans;
    }

    public static String count(String s){
        int count = 1;
        char cur = s.charAt(0);
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 1; i < s.length(); i++) {
            if (cur == s.charAt(i)) {
                count++;
            } else {
                stringBuilder.append(count);
                stringBuilder.append(cur);
                count = 1;
                cur = s.charAt(i);


            }
        }
        stringBuilder.append(count);
        stringBuilder.append(cur);
        return stringBuilder.toString();
    }


}
